Computers are subject to external attacks that can affect their operation. These attacks seek to exploit flaws in the software. The ultimate result of this exploitation is to subvert execution and gain control of the software behavior—in a sense, hijack the computer.
One of the methods used to protect against the hijacking of computer software is the use of the enforcement of Control Flow Integrity (“CFI”). CFI is a binary transformation method that protects indirect control transfers in the form of calls, returns and indirect jumps, and by tagging control transfers and valid destinations with identifier strings. A control transfer can only jump to an address if the tag at the destination matches the tag at the control transfer. Each control transfer may have many potential targets, which will all have identical tags. Any transfers that target the same address also will have identical tags.
The purpose of CFI systems is to limit the control flow of programs to only control transfers that exist in the program when operating normally. These systems will validate return addresses and functions pointers at runtime to prevent attackers from redirecting control to arbitrary addresses. As such, attempted attacks to hijack the control flow can only redirect the control flow to a limited set of locations that have been explicitly allowed rather than to any location in the address space.
As to CFI enforcement, it is carried out through the use of a Control Flow Graph (“CFG”). The CFG dictates the software execution path. Conventionally, the CFG can be defined by analysis, such as, source-code analysis, binary analysis, or execution profiling. CFI enforcement that uses CFG has been found to be effective against a range of common attacks since abnormal control-flow modifications is an essential step in many exploits.
When implemented during program execution, CFI requires that whenever a machine-code instruction transfers control, it targets a valid destination as defined by a CFG created ahead of time. Since most instructions target a consistent destination, this requirement can usually be handled statically. However, for computed control-flow transfers, which are those whose destination is determined at runtime, this requirement must be handled with a dynamic check. Machine-code rewriting is a relatively straightforward strategy for implementing dynamic checks, but certain issues do exist. One in particular is a rewritten program no longer uses the same code memory and all memory addresses in the program must be adjusted accordingly. However, there are available tools to mitigate some of these issues.
CFI instrumentation modifies each source instruction and each possible destination instruction of computed control-flow transfers. Two destinations are equivalent when the CFG contains edges to each of the same set of sources. For example, if the CFG contains edges to two destinations from a common source, then the destinations are equivalent. At each destination, the CFI instrumentation inserts a bit pattern, or ID, that identifies an equivalent class of destinations. The CFI instrumentation also inserts a dynamic check, or ID-check, before each source that ensures the runtime destination has the ID of the proper equivalent class. CFI instrumentation uses specific machine-code sequences for ID-checks and IDs.
As part of CFI enforcement, there is a measurement of the overhead required for the CFI instrumentation. Typically, the size of the binary after CFG construction and CFI implementation increased on average by 8%. This overhead is viewed as an increase in runtime.
FIG. 1, generally at 100, shows a representative drawing of CFI enforcement overhead for a number of benchmarks. Benchmarks 102 are common Standard Performance Evaluation Corporation 2000 (“SPEC”) computation benchmarks. As shown, the normalized overhead 104 for CFI enforcement increases the running time for each CFI-instrumented benchmark at 102 relative to the runtime of the original benchmark binaries. On average, shown at AVG 106, the benchmarks took approximately 16% longer to execute with the measured overhead ranging from 0 to 45%. This overhead results from a number of factors, including increased cache pressure.
CFI provides strong guarantees that the control flow of a running program does not deviate from its CFG. If the CFG is a perfect representation of the control flow of a binary, then it will be difficult for an attacker to get arbitrary code execution. However, enforcing an arbitrary CFG can have serious overhead implications and it can be very difficult to generate a CFG that is a perfect representation of a binary.
Conventional systems, as described above, necessitate that the structure of the identification labels requires a rigorous implementation process that generally renders widespread or commercial application unfeasible. This is based on the need to attach a unique identifier to each call-destination and return-destination pairing, and restrict the range of valid indirect call flow transfer targets from a call or return instruction to a single destination specifically paired to that origin. Such a system provides some security but also entails the development and insertion of unique identifiers for every individual transfer pairing in the program's control flow architecture.
To generate a control flow protection scheme of that degree, it relies on a number of assumptions that in reality are impractical. The first assumption is the process presumes the development of, and access to, a CFG of the program to be shielded by the CFI protections. The second assumption is the instrumentation framework could be constructed because there was full knowledge of the code symbols indicating the locations of indirect transfers and returns. And, the third assumption is the instrumentation would be designed for potential application only to programs that incorporate its protections before the code is compiled and, as such, there could be strong familiarity with the knowledge of the code.
There are other systems that provide methods to prevent hijacking of software programs. One such system restricts indirect control flow transfers by routing all transfers through an intermediary springboard system. Therefore, rather than allowing indirect transfers to occur, the system generates an interceding switchboard code to which any attempted indirect transfers are redirected in a manner that effectively transforms indirect transfers into direct transfers to the intermediary target rather than to the target of the code. At the springboard, a fabricated transfer is executed that serves as the indirect transfer, and then a direct transfer from the springboard location to the intended target of the original direct transfer occurs. Any indirect transfers are thus contained within the intermediary springboard. This method has some effectiveness but it also adds a larger level of complexity to the handling of indirect transfers.
Another method sorts transfer targets and origins into various predetermined categories. Indirect transfers are subsequently restricted from certain classifications of origins to a limited set of target categories based on the origin's classification. This method relies on a control flow map produced using a linear recursive mapping process. Any indirect transfer in the system is permitted only if it is proposed target is within the group of target classifications with which the transfer's origin point is paired. Again, this system adds undue complexity to the handling of transfers and also restricts these transfers to a finite subset, which may not be desirable.
Yet another protection system generates instrumented code only immediately prior to runtime. This system relies on access to assembly/disassembly methods for that process. Although, the system may have certain efficacy, it does not provide significant advantages over other conventional systems.
The present invention is able to solve the problems of conventional systems to provide a system that requires less average overhead and does not require all of the complications of the other systems described above yet it provides an improved CFI system and method that may be implemented more effectively.